1. Field of the Invention
The present invention relates to coding and decoding methods for error correcting codes used for correcting data errors, and further relates to coding and decoding devices corresponding to such methods.
2. Description of the Related Art
In the fields of information processing and telecommunication, it is required to detect and correct errors occurring at the time of transmitting, receiving, and storing information symbol sequences, i.e., data generated by binarizing information to be transmitted, such as texts, still images, moving images, and voice. Errors occur in data due to noises and imperfect media at the time of executing network communications, writing and reading of data to and from storage media such as digital versatile discs (DVD) and flash memories. In order to deal with the occurrence of such errors, using redundancy codes which are added to original data beforehand, it is determined whether any error has occurred, and the original data is reproduced even if any error is detected. In other words, redundancy codes are added to the original data to convert the data into a codeword sequence. Such a codeword sequence with redundancy is referred to as an “error correcting code”.
Non-volatile semiconductor memories called flash memories are becoming smaller in size and larger in terms of their capacity. Such flash memories have a storage area including a plurality of uniformly sized blocks, and each block includes a plurality of uniformly sized pages. Data are erased from a flash memory on a block-by-block basis, and read out of and written into a flash memory on a page-by-page basis. Flash memories have gained larger storage capacity through miniaturization and multi-level cell technology. A side effect of larger storage capacity is an increasing number of error bits. It is a common practice to correct errors with the use of an error correcting code (ECC). Examples of error correcting codes include BCH, Reed-Solomon, and low-density parity-check (LDPC) codes.
In a flash memory, data in one page are divided and stored in four sections, for example. In other words, four sections placed side by side constitute a single page. Each such section stores one error correcting code. The error correcting code includes a parity check symbol (redundant bits) corresponding to a specific error correction coding scheme in addition to information symbols (original data). If the same coding method is used, error correction performance improves when the number of redundant bits is larger. The number of redundant bits is on the rise as the memory cells utilize multi-level technologies and miniaturization advances, or as higher reliability is required. On the other hand, as the number of redundant bits increases, and the number of correctable error bits, which is determined in accordance with the number of redundant bits, increases, circuitry for error correction becomes larger. This increase in circuit size means a smaller area for data storage and a smaller storage capacity. The increased numbers of redundant bits and correctable error bits also lead to increased time required for reading and reproducing user data. Accordingly, it is required to improve the error correcting performance without increasing the number of redundant bits.
It is similarly important in the field of telecommunication to improve error correcting performance. With the increased communication line speed, a higher error correcting performance is required with limited physical resources. In this specification and claims, the term “page”, which is used mainly in the field of storage medium, is primarily used. This term “page”, generally refers to data of one unit and also include concepts used in the field of communication such as “transmit data block” and “transport block”. For example, the concept “transport block” is used in the long-term evolution (LTE) standards or the evolved universal terrestrial radio access (E-UTRA) standards by the standardizing body 3GPP, and these are equivalent to the term “page”.
JP A 2008-108297 describes a non-volatile semiconductor storage device improved in error correction efficiency by mixing a high-error rate portion with a low-error rate portion in a single ECC frame and thus evening out location-dependent fluctuations in error rate among ECC frames.
JP A 2011-003975 describes a technique for generating a transport block codeword by dividing a transport block into a plurality of code blocks so that each code block includes a part of another code block, generating code block codewords by executing error correction coding processing to each of the plurality of code blocks, and combining the code block codewords together. In all examples illustrated in the drawings, an overlap portion is provided between a leftmost-end code block and a rightmost-end code block.